package cn.szq.concurrent.thread.interview;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.stream.IntStream;

/**
 * @ClassName: HashCode
 * @Description:
 * @Author: szq
 * @Date: 2021-10-13 15:25:46
 */
public class HashCode {

    public static Integer hashcode(String str, Integer multiplier){
        int hash = 0;
        for(int i=0; i<str.length(); i++){
            hash = multiplier * hash + str.charAt(i);
        }
        return hash;
    }

    /**
     * 计算Hash碰撞概率
     */
    public static RateInfo hashCollisionRate(Integer multiplier, List<Integer> hashcodeList){
        int maxHash = hashcodeList.stream().max(Integer::compareTo).get();
        int minHash = hashcodeList.stream().min(Integer::compareTo).get();

        int collisionCount = (int) (hashcodeList.size() - hashcodeList.stream().distinct().count());

        return new RateInfo(maxHash, minHash, multiplier,collisionCount, collisionCount*1.0/hashcodeList.size());
    }

    public static List<RateInfo> collisionRateList(Set<String> strList, Integer... multipliers) {
        List<RateInfo> rateInfoList = new ArrayList<>();
        for(Integer multiplier : multipliers){
            List<Integer> hashcodeList = new ArrayList<>();
            for(String str : strList){
                Integer hashcode = hashcode(str, multiplier);
                hashcodeList.add(hashcode);
            }
            rateInfoList.add(hashCollisionRate(multiplier, hashcodeList));
        }
        return rateInfoList;
    }

    public static void main(String[] args) {
        System.out.println("*******************************************");
        System.out.println(HashCode.hashcode("aaa", 31));
        System.out.println("*******************************************");

        Set<String> words = FileUtil.readWordList("E:/learning/concurrent-programming/src/main/resources/103976个英语单词库.txt");
        List<RateInfo> rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
        for (RateInfo rate : rateInfoList) {
            System.out.println(String.format("乘数 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
        }

        System.out.println("*******************************************");

        List<Integer> nums = new ArrayList<>(100);
        IntStream.rangeClosed(1,100).forEach(t->nums.add(t));
        RateInfo rate = HashCode.hashCollisionRate(31, nums);
        System.out.println(String.format("乘数 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));

    }


}
